﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using UnityEngine;

/// <summary>
/// 最长非降序子序列
/// longest increasing subsequence
/// </summary>
public class DP_LIS:MonoBehaviour
{
    private int[] nums = new int[] { 5,3,4,8,6,7 };

    public void Start()
    {
        Debug.Log( CalculateLIS());
    }

    private int CalculateLIS()
    {
        int[] length = new int[nums.Length];
        int returnLen = 1;
         for(int i = 0; i < nums.Length; i++)
        {
            length[i] = 1;
            for(int j=0; j < i; j++)
            {
                if (nums[i] >= nums[j] && length[i] < length[j] + 1) 
                {
                    length[i] = length[j] + 1;
                }
            }
            if (length[i] > returnLen)
            {
                returnLen = length[i];
            }
        }
        return returnLen;
    }
}
